With continuous advances in communications technology, link transmission speeds of Internet backbone networks have been increasing rapidly. In turn, this increase in network speeds demands more powerful Internet Protocol (IP) address lookup engines. For example, when receiving a packet by an Internet router, IP routing including IP route lookup can be one of the most time consuming operations, especially in Classless Inter-Domain Routing (CIDR) where Longest Prefix Matching (LPM) algorithms are employed. In addition, due to the increasing link bandwidth and the proliferation of real-time services, average packet sizes are continuously decreasing. As a result, because an Internet router typically performs one lookup per packet, this trend can be expected to increase the number of lookups per second at a rate faster than linear.
Ternary Content Addressable Memory (TCAM) is a fully associative memory that allows a “don't care” state to be stored in each memory cell in addition to zeros (0) and ones (1). For example, when a destination address is presented to a typical TCAM, each TCAM entry can be looked up in parallel, and the longest prefix that matches the address can be returned. Thus, a single TCAM access can be sufficient to perform a route lookup operation, in contrast to conventional ASIC-based designs that use many tries that can require multiple memory accesses for a single route lookup. Accordingly, routing latencies for TCAM-based routing tables can be significantly lower than conventional ASIC-based tables. As a result, TCAMs can return a matching result within only one memory access, which is typically much faster than software algorithmic approaches that require multiple memory accesses. Accordingly, TCAMs can be well-suited for high performance parallel lookups, and thus, TCAMs are widely employed for such IP route lookups in Internet domain routing.
Nevertheless, TCAM is not necessarily a panacea. For instance, memory access speed for TCAMs is slower than for conventional memories (e.g., Static random-access memory (SRAM), dynamic random-access memory (DRAM), etc.) while the power consumption is relatively higher. In addition, the size of route tables have been increasing at a rate of about 10-50 thousand entries per year. As can be expected with the proliferation of Internet Protocol version 6 (IPv6) deployments, even more route table storage will be needed.
For example, an increasing speed gap between logic function units, such as central processing unit (CPU), and memory. For instance, for the last few decades, speeds of logic units have been greatly developed while improvements in memory speeds have not matched pace. In addition, memory prices have decreased dramatically while larger memory sizes becomes available. As an example, a one gigabyte DRAM currently costs less than $10 U.S. In contrast with the high price and limited storage of TCAM, the gap of storage capacity between conventional memory and TCAM is getting larger and larger. Thus, it can be expected that, as link rates increase and route table sizes exceed limited storage capacities, the high power consumption and high costs associated with scaling TCAM implementations can result in further restrictions on application of TCAM in IP route lookup applications.
The above-described deficiencies are merely intended to provide an overview of some of the problems encountered in efficient lookup scheme design, and are not intended to be exhaustive. Other problems with the state of the art may become further apparent upon review of the description of the various non-limiting embodiments of the disclosed subject matter that follows.